插入排序

基本思想：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过为止。

算法过程描述：

从第一个元素开始，可认为该元素已被排序；
取出下一个元素（记为当前元素），在已排序的元素序列中从后向前扫描；
若被扫描到的已排序元素大于当前元素，则将该已排序元素移到下一位置；
重复步骤3，直到找到已排序元素小于等于当前元素的位置；
将当前元素插入到该位置后；
重复步骤2至步骤5，直到完成排序。

移位法

JavaScript

const insertionSort = A => {
  for (let i = 1; i < A.length; i++) {
    // i-1 为已排序元素的末位
    let [j, cur] = [i - 1, A[i]] // 向后移位时会被覆盖，先缓存
    while (j >= 0 && A[j] > cur) {
      A[j + 1] = A[j]
      j--
    }
    A[j + 1] = cur // 该位置后插入
  }
}

稳定性：

若将 第5行 代码中的>改为>=，该算法将不再是稳定排序算法！

交换法

JavaScript

const insertionSort = A => {
  for (let i = 1; i < A.length; i++) {
    let j = i - 1
    while (j >= 0 && A[j] > A[i]) { // 一直交换，直到找到合适的位置
      [A[j], A[i]] = [A[i], A[j]]
      j--
    }
  }
}

稳定性：

若将 第4行 代码中的>改为>=，该算法将不再是稳定排序算法！

插入排序 ​

移位法 ​

交换法 ​

插入排序

移位法

交换法